PRD算法中的数学

PRD算法介绍

锋利的吊丝：保底机制的简单介绍4 赞同 · 0 评论 文章

上一篇文章介绍了一种简单易懂的保底机制，在本篇文章中对它进行简修改，变成很多游戏中都在使用的PRD算法。下面的网站对PRD算法的由来和细节进行了详细介绍，

PRD算法是一种随机的保底机制，与上一篇文章类似，如果一个事件连续 ${\displaystyle N-1}$\displaystyle N-1 次没有成功的话，那么第 ${\displaystyle N}$\displaystyle N 次一定成功。但与前一篇文章不同的是，在第 ${\displaystyle N}$\displaystyle N 次之前的每一次成功概率不是常数，而是会随着失败次数线性增长，直至达到 ${\displaystyle 1}$\displaystyle 1。具体来说就是，给定常数 ${\displaystyle 0<c<1}$\displaystyle 0< c< 1，假设在某个时间，距离最近一次成功之后又连续失败了 ${\displaystyle k-1}$\displaystyle k-1 次，那这次成功的概率是 ${\displaystyle kc}$\displaystyle kc ，随着连续失败次数$\displaystyle k$增加，总会有一次成功概率 ${\displaystyle kc⩾1}$\displaystyle kc\geqslant 1，那这一次就一定会成功。设 ${\displaystyle N=min\{k|kc⩾1\}=min\{k|k⩾1/c\}=\lceil 1/c\rceil }$\displaystyle N=\min\{k|kc\geqslant 1\} =\min\{k|k\geqslant 1/c\} =\lceil 1/c\rceil 在这个算法下，事件最多连续失败 ${\displaystyle N-1}$\displaystyle N-1 次，这说明名义概率 ${\displaystyle p}$\displaystyle p 一定不小于 ${\displaystyle 1/N}$\displaystyle 1/N。

这里我们将用上一篇文章介绍的两种方法来找到 ${\displaystyle c}$\displaystyle c 与 ${\displaystyle p}$\displaystyle p 的关系，学会后大家可以对前面的算法进行修改，例如将线性增长改为非线性变化，并计算出对应的名义概率。

方法1：

第 ${\displaystyle 1}$\displaystyle 1 次就成功的概率是 ${\displaystyle c}$\displaystyle c，恰好第 ${\displaystyle 2}$\displaystyle 2 次成功的概率是 ${\displaystyle (1-c)2c}$\displaystyle ( 1-c) 2c，恰好第 ${\displaystyle 3}$\displaystyle 3 次成功的概率是 ${\displaystyle (1-c)(1-2c)3c}$\displaystyle ( 1-c)( 1-2c) 3c，对于 ${\displaystyle 1⩽k⩽N-1}$\displaystyle 1\leqslant k\leqslant N-1，恰好在第 ${\displaystyle k}$\displaystyle k 次成功的概率是 ${\displaystyle (1-c)(1-2c)\cdots (1-(k-1)c)kc}$\displaystyle ( 1-c)( 1-2c) \cdots ( 1-( k-1) c) kc，而恰好在第 ${\displaystyle N}$\displaystyle N 次才成功，也就是前 ${\displaystyle N-1}$\displaystyle N-1 次都失败的概率是 ${\displaystyle (1-c)(1-2c)\cdots (1-(N-1)c)}$\displaystyle ( 1-c)( 1-2c) \cdots ( 1-( N-1) c)。所以成功所花时间的期望是 $$\begin{array}{rl}E& =\sum _{k=1}^{N-1}k(1-c)(1-2c)\cdots (1-(k-1)c)kc+N(1-c)(1-2c)\cdots (1-(N-1)c)\\ & =c\sum _{k=1}^{N-1}{k}^2[\prod _{j=1}^{k-1}(1-jc)]+N\prod _{j=1}^{N-1}(1-jc)\end{array}$$\begin{aligned} E & =\sum _{k=1}^{N-1} k( 1-c)( 1-2c) \cdots ( 1-( k-1) c) kc+N( 1-c)( 1-2c) \cdots ( 1-( N-1) c)\\ & =c\sum _{k=1}^{N-1} k^{2}\left[\prod _{j=1}^{k-1}( 1-jc)\right] +N\prod _{j=1}^{N-1}( 1-jc) \end{aligned}\\看起来挺难化简的，所以名义概率 ${\displaystyle p}$\displaystyle p $$p=\frac{1}{E}=\frac{1}{c\sum _{k=1}^{N-1}{k}^2[\prod _{j=1}^{k-1}(1-jc)]+N\prod _{j=1}^{N-1}(1-jc)}$$ p=\frac{1}{E} =\frac{1}{c\sum _{k=1}^{N-1} k^{2}\left[\prod _{j=1}^{k-1}( 1-jc)\right] +N\prod _{j=1}^{N-1}( 1-jc)}\\这是用 ${\displaystyle c}$\displaystyle c 计算 ${\displaystyle p}$\displaystyle p 的公式。通常我们是指定名义概率 ${\displaystyle p}$\displaystyle p，需要求出对应的 ${\displaystyle c}$\displaystyle c，可以想象名义概率 ${\displaystyle p}$\displaystyle p 是 ${\displaystyle c}$\displaystyle c 的严格递增函数，所以利用二分查找即可。很多介绍PRD算法的文章用这个方法给出 ${\displaystyle p}$\displaystyle p 和 ${\displaystyle c}$\displaystyle c 的对照表

方法2：

构建Markov链，与上一篇文章一样，状态空间为 ${\displaystyle S=\{0,1,2,\cdots ,N-1\}}$\displaystyle S=\{0,1,2,\cdots ,N-1\} 共 ${\displaystyle N}$\displaystyle N 个元素， ${\displaystyle Z_t}$\displaystyle Z_{t} 表示在最近一次成功之后又连续失败了几次，转移图如下

容易看出是不可约，非周期的。转移矩阵为 $$P=\left(\begin{array}{ccccccc}c& 1-c& & & & & \\ 2c& & 1-2c& & & & \\ 3c& & & 1-3c& & & \\ ⋮& & & & \ddots & & \\ (N-1)c& & & & & 1-(N-1)c& \\ 1& & & & & 0& \end{array}\right)\begin{array}{c}0\\ 1\\ 2\\ ⋮\\ N-2\\ N-1\end{array}$$P=\begin{pmatrix} c & 1-c & & & & & \\ 2c & & 1-2c & & & & \\ 3c & & & 1-3c & & & \\ \vdots & & & & \ddots & & \\ ( N-1) c & & & & & 1-( N-1) c & \\ 1 & & & & & 0 & \end{pmatrix}\begin{matrix} 0\\ 1\\ 2\\ \vdots \\ N-2\\ N-1 \end{matrix} \\唯一平稳分布 ${\displaystyle \pi =({\pi }_0,{\pi }_1,\cdots ,{\pi }_{N-1})}$\displaystyle \pi =( \pi _{0} ,\pi _{1} ,\cdots ,\pi _{N-1}) 满足 $$\{\begin{array}{l}\pi P=\pi \\ \pi \mathbf{1}=1\end{array}$$\begin{cases} \pi P=\pi \\ \pi \mathbf{1} =1 \end{cases}\\ 得到$$\{\begin{array}{l}c{\sum }_{i=0}^{N-2}(i+1){\pi }_i+{\pi }_{N-1}={\pi }_0\\ (1-ic){\pi }_{i-1}={\pi }_i,i=1,\cdots ,N-1\\ {\sum }_{i=0}^{N-1}{\pi }_i=1\end{array}$$\begin{cases} c\sum\nolimits _{i=0}^{N-2}( i+1) \pi _{i} +\pi _{N-1} =\pi _{0}\\ ( 1-ic) \pi _{i-1} =\pi _{i} ,\ i=1,\cdots ,N-1\\ \sum\nolimits _{i=0}^{N-1} \pi _{i} =1 \end{cases}\\ 仿照上篇文章里的分析过程， ${\displaystyle {\pi }_i={\pi }_0[{\prod }_{j=0}^i(1-jc)]}$\displaystyle \pi _{i} =\pi _{0}\left[\prod\nolimits _{j=0}^{i}( 1-jc)\right]，代入第一个方程得到恒等式$$c{\sum }_{i=0}^{N-2}(i+1)[\prod _{j=0}^i(1-jc)]+\prod _{j=0}^{N-1}(1-jc)\equiv 1$$c\sum\nolimits _{i=0}^{N-2}( i+1)\left[\prod\limits _{j=0}^{i}( 1-jc)\right] +\prod\limits _{j=0}^{N-1}( 1-jc) \equiv 1\\列出这个方程的前提条件是 ${\displaystyle (N-1)c<1⩽Nc}$\displaystyle ( N-1) c< 1\leqslant Nc。不过观察可知，等式的左边是 ${\displaystyle c}$\displaystyle c 的多项式，右端是 ${\displaystyle 0}$\displaystyle 0 次多项式，这两个多项式在区间 ${\displaystyle c\in [1/N,1/(N-1))}$\displaystyle c\in [ 1/N,1/( N-1)) 上相等，所以对于任何复数 ${\displaystyle c}$\displaystyle c，左边端都是常数 ${\displaystyle 1}$\displaystyle 1。挺神奇的，我不知道这个等式怎么通过其他方法证明。对于特殊的情况 ${\displaystyle c=1/N}$\displaystyle c=1/N，等式变为 $$\begin{array}{rl}1& \equiv \frac{1}{N}{\sum }_{i=0}^{N-1}(i+1)\left[\prod _{j=0}^i(1-\frac{j}{N})\right]\\ & =\frac{1}{N}{\sum }_{i=0}^{N-1}\frac{(N-1)!(i+1)}{(N-i-1)!N^i}\\ & =\frac{1}{N}{\sum }_{i=1}^N\frac{i\times N!}{(N-i)!N^i}\end{array}$$\begin{aligned} 1 & \equiv \frac{1}{N}\sum\nolimits _{i=0}^{N-1}( i+1)\left[\prod\limits _{j=0}^{i}\left( 1-\frac{j}{N}\right)\right]\\ & =\frac{1}{N}\sum\nolimits _{i=0}^{N-1}\frac{( N-1) !( i+1)}{( N-i-1) !N^{i}}\\ & =\frac{1}{N}\sum\nolimits _{i=1}^{N}\frac{i\times N!}{( N-i) !N^{i}} \end{aligned}\\用Mathematica验算了一下，还真是对的。

回到我们的主题，把 ${\displaystyle {\pi }_i={\pi }_0[{\prod }_{j=0}^i(1-jc)]}$\displaystyle \pi _{i} =\pi _{0}\left[\prod\nolimits _{j=0}^{i}( 1-jc)\right] 代入 ${\displaystyle {\sum }_{i=0}^{N-1}{\pi }_i=1}$\displaystyle \sum\nolimits _{i=0}^{N-1} \pi _{i} =1，得到 ${\displaystyle {\pi }_0\left\{{\sum }_{i=0}^{N-1}[{\prod }_{j=0}^i(1-jc)]\right\}=1}$\displaystyle \pi _{0}\left\{\sum\nolimits _{i=0}^{N-1}\left[\prod\nolimits _{j=0}^{i}( 1-jc)\right]\right\} =1，所以$$\begin{array}{rl}{\pi }_0& =\frac{1}{\sum _{i=0}^{N-1}[{\prod }_{j=0}^i(1-jc)]}\\ {\pi }_i& ={\pi }_0[\prod _{j=0}^i(1-jc)]=\frac{\prod _{j=0}^i(1-jc)}{\sum _{k=0}^{N-1}[\prod _{j=0}^k(1-jc)]},i=0,1,\cdots ,N-1\end{array}$$\begin{aligned} \pi _{0} & =\frac{1}{\sum\limits _{i=0}^{N-1}\left[\prod\nolimits _{j=0}^{i}( 1-jc)\right]}\\ \pi _{i} & =\pi _{0}\left[\prod\limits _{j=0}^{i}( 1-jc)\right] =\frac{\prod\limits _{j=0}^{i}( 1-jc)}{\sum\limits _{k=0}^{N-1}\left[\prod\limits _{j=0}^{k}( 1-jc)\right]} ,\ i=0,1,\cdots ,N-1 \end{aligned}\\方法1和方法2的结果肯定是相同的，所以我们惊讶地发现，方法1中那个看起来没法化简的公式，事实上有个稍微简单一点的形式$$E=c\sum _{k=1}^{N-1}{k}^2[\prod _{j=0}^{k-1}(1-jc)]+N\prod _{j=0}^{N-1}(1-jc)\equiv \sum _{i=0}^{N-1}[\prod _{j=0}^i(1-jc)]$$E=c\sum _{k=1}^{N-1} k^{2}\left[\prod _{j=0}^{k-1}( 1-jc)\right] +N\prod _{j=0}^{N-1}( 1-jc) \equiv \sum\limits _{i=0}^{N-1}\left[\prod\limits _{j=0}^{i}( 1-jc)\right]\\再次惊了，这两个 ${\displaystyle c}$\displaystyle c 的多项式居然是一样的，数值验证了一下确实相等，我们又证明了一个怪怪恒等式。

补充内容：我知道这个等式怎么证明了，对于取值为非负整数的随机变量 ${\displaystyle X}$\displaystyle X，一定有如下等式
$$E(X)=\sum _{n=1}^{\mathrm{\infty }}nP(X=n)=\sum _{n=1}^{\mathrm{\infty }}P(X⩾n)$$E( X) =\sum _{n=1}^{\infty } nP( X=n) =\sum _{n=1}^{\infty } P( X\geqslant n)\\上式就是把 ${\displaystyle P(X=n)}$\displaystyle P( X=n) 和 ${\displaystyle P(X⩾n)}$\displaystyle P( X\geqslant n) 分别代入的结果，这个化简可以在方法1中就得到。

写代码时用右端的公式应该会稍微简单一点，在计算大于等于的概率时，循环中每一步只需要一次乘法与一次加法。我去翻了很多介绍PRD算法的文章，都是用方法1里的公式来编写代码的。只有一个例外，

Calculating the constant C in Dota 2 pseudo-random distribution​gaming.stackexchange.com/questions/161430/calculating-the-constant-c-in-dota-2-pseudo-random-distribution

其中的一个答案也说了用Markov链可以解释PRD算法，他的代码是构造完转移矩阵 ${\displaystyle P}$\displaystyle P 后，计算了矩阵 ${\displaystyle P}$\displaystyle P 最大特征值 ${\displaystyle 1}$\displaystyle 1 对应的唯一特征向量，并归一化，理论上这与我们的结果也是一样的，但是看起来计算复杂度也会更高一些。

然后我们再用高贵的Mathematica帮我们化简一些特殊情形，取 ${\displaystyle c=1/N}$\displaystyle c=1/N 得到 $$\begin{array}{rl}E& =\sum _{i=0}^{N-1}\left[\prod _{j=0}^i(1-\frac{j}{N})\right]\\ & =\frac{1}{N}\sum _{i=0}^{N-1}\frac{N!}{(N-i-1)!N^i}\\ & =N{\left(\frac{e}{N}\right)}^N{\int }_N^{\mathrm{\infty }}{x}^{N-1}{e}^{-x}\mathrm{d}x\cdots (Mathematica)\end{array}$$\begin{aligned} E & =\sum\limits _{i=0}^{N-1}\left[\prod\limits _{j=0}^{i}\left( 1-\frac{j}{N}\right)\right]\\ & =\frac{1}{N}\sum\limits _{i=0}^{N-1}\frac{N!}{( N-i-1) !N^{i}}\\ & =N\left(\frac{e}{N}\right)^{N}\int _{N}^{\infty } x^{N-1} e^{-x} \ \mathrm{d} x\ \cdots ( Mathematica) \end{aligned}\\

这大概是把阶乘写成留数以后化简得到的吧。

容易看出 ${\displaystyle E={\sum }_{i=0}^{N-1}[{\prod }_{j=0}^i(1-jc)]}$\displaystyle E=\sum\nolimits _{i=0}^{N-1}\left[\prod\nolimits _{j=0}^{i}( 1-jc)\right] 在 ${\displaystyle c\in [1/N,1/(N-1))}$\displaystyle c\in [ 1/N,1/( N-1)) 上递减，所以名义概率 $p={\pi }_0=1/E$p=\pi _{0} =1/E 确实是 ${\displaystyle c}$\displaystyle c 的增函数，可以放心使用二分查找。

PRD机制在低概率下的表现

保底机制本意是不希望大家的运气太差，出现连续失败的情况。在独立随机中，如果名义概率 ${\displaystyle p}$\displaystyle p 比较大，那么出现连续失败的概率也不会太大（当然如果遇到了的话肯定还是非常不爽的）。而如果名义概率 ${\displaystyle p}$\displaystyle p 本身就较低，在独立情况下，连续失败将不可避免。假设 ${\displaystyle T}$\displaystyle T 是名义概率 ${\displaystyle p}$\displaystyle p 下首次成功的时间。在独立的情况下， ${\displaystyle T}$\displaystyle T 服从几何分布 ${\displaystyle Geo(p)}$\displaystyle Geo( p)，且对于正整数 ${\displaystyle t}$\displaystyle t $$P(T>t|独立)=(1-p{)}^t$$P( T >t|独立) =( 1-p)^{t}\\对于较大的实数 ${\displaystyle t}$\displaystyle t，将上式中的等号改成约等于也是成立的。平均 ${\displaystyle E(T)=1/p}$\displaystyle E( T) =1/p 次会成功一次，我们来估算一下在 ${\displaystyle 2}$\displaystyle 2 倍期望次数后都没有成功的概率 $$P(T>\frac{2}{p}|独立)\approx (1-p{)}^{\frac{2}{p}}\approx e^{-2}\approx 0.135335$$P\left( T >\frac{2}{p} |独立\right) \approx ( 1-p)^{\frac{2}{p}} \approx e^{-2} \approx 0.135335\\上式第二个约等号来自于高数中最基础的一个极限 $$\underset{n\to \mathrm{\infty }}{lim}{(1+\frac{1}{n})}^n=e$$ \lim _{n\rightarrow \infty }\left( 1+\frac{1}{n}\right)^{n} =e\\这说明在独立随机中，如果概率 ${\displaystyle p}$\displaystyle p 比较小，那大概有 ${\displaystyle 13.5\mathrm{\%}}$\displaystyle 13.5\% 的人在 ${\displaystyle 2}$\displaystyle 2 倍期望以后才成功，将上面的 ${\displaystyle 2}$\displaystyle 2 改成其他数字也是成立的，大概会有 ${\displaystyle e^{-3}\approx 4.98\mathrm{\%}}$\displaystyle e^{-3} \approx 4.98\% 的玩家在 ${\displaystyle 3}$\displaystyle 3 倍期望， ${\displaystyle e^{-4}\approx 1.83\mathrm{\%}}$\displaystyle e^{-4} \approx 1.83\% 的玩家在$\displaystyle 4$倍期望， ${\displaystyle e^{-5}\approx 0.67\mathrm{\%}}$\displaystyle e^{-5} \approx 0.67\% 的玩家在 ${\displaystyle 5}$\displaystyle 5 倍期望后才成功。。。。这个比例可以说非常高了，如果一个游戏有几万个玩家，那这部分玩家会给游戏带来大量的差评。

在PRD算法下，运气最差会在第 ${\displaystyle N=\lceil 1/c\rceil \approx 1/c}$\displaystyle N=\lceil 1/c\rceil \approx 1/c 时成功，也就是说 ${\displaystyle P(T>N|\mathrm{P}\mathrm{R}\mathrm{D})=0}$\displaystyle P( T >N|\mathrm{PRD}) =0，那独立情况下这个概率是多大呢 $$P(T>N|独立)\approx (1-p{)}^N\approx (1-p{)}^{\frac{1}{c}}=(1-p{)}^{\frac{1}{p}\frac{p}{c}}\approx e^{-\frac{p}{c}}$$ \ P( T >N|独立) \approx ( 1-p)^{N} \approx ( 1-p)^{\frac{1}{c}} =( 1-p)^{\frac{1}{p}\frac{p}{c}} \approx e^{-\frac{p}{c}}\\那 ${\displaystyle p/c}$\displaystyle p/c 是多少呢，首先一个显然的结论是 ${\displaystyle c}$\displaystyle c 一定是严格小于名义概率 ${\displaystyle p}$\displaystyle p 的，可以回去看一下那张表格感受一下 ${\displaystyle c}$\displaystyle c 与 ${\displaystyle p}$\displaystyle p 之间的差距，在 ${\displaystyle p⩽0.4}$\displaystyle p\leqslant 0.4 时， ${\displaystyle p/c⩾2}$\displaystyle p/c\geqslant 2，名义概率越小， ${\displaystyle p/c}$\displaystyle p/c 越大，相应的 ${\displaystyle P(T>N|独立)}$\displaystyle \ P( T >N|独立) 也越接近于 ${\displaystyle 0}$\displaystyle 0。 例如 ${\displaystyle p=0.05}$\displaystyle p=0.05 时， ${\displaystyle c\approx 0.00380166}$\displaystyle c\approx 0.00380166， ${\displaystyle N=264}$\displaystyle N=264，PRD机制只能保证最坏 ${\displaystyle 264}$\displaystyle 264 次才成功的情况，这个数是平均次数 ${\displaystyle 1/0.05=20}$\displaystyle 1/0.05=20 的 ${\displaystyle 13.2}$\displaystyle 13.2 倍，在这么大的 ${\displaystyle N}$\displaystyle N 下 ${\displaystyle P(T>N|独立)\approx 1.3153\times {10}^{-6}}$\displaystyle P( T >N|独立) \approx 1.3153\times 10^{-6}，本身已经很小了。也就说 ${\displaystyle p=0.05}$\displaystyle p=0.05 的情况下，PRD算法与独立算法相比，好像并未有效地进行保底。而且我们取的 ${\displaystyle p=0.05}$\displaystyle p=0.05 其实并不算很小，在很多抽卡游戏里，名义概率比这小得多，在这种情况下，使用PRD算法，将会导致灾难性的体验，并不会比独立随机好太多。

如果之后有空的话，我们来比较一下PRD算法给出的成功耗时分布与独立情形对应的几何分布，算算他们之间全变差或者Wasenstein距离，看看他们的差距到底有多大，是否真的起到了良好的保底效果。

保底机制的扩展

原神的 ${\displaystyle 1.6\mathrm{\%}}$\displaystyle 1.6\% 概率对应平均 ${\displaystyle 62.5}$\displaystyle 62.5 次出五星，而原神给的保底次数是 ${\displaystyle 90}$\displaystyle 90 次，也就是说最大次数大概是平均次数的 ${\displaystyle 1.5}$\displaystyle 1.5 倍，我觉得这也是玩家比较能接受的数值，因为如果这个倍数再大一些，就会有一部分运气差的玩家觉得自己与平均水平的严重偏离。我们可以认为，如果一个保底算法的最大次数不超过平均次数的 ${\displaystyle 1.5}$\displaystyle 1.5 倍是比较合理的。我们来看看在这个意义下PRD算法在什么情况下是合理的，回去翻看表格，会得到一个很意外的情况，差不多当 ${\displaystyle p>0.55}$\displaystyle p >0.55 时，这个保底机制才是合理的，在Dota2中只有很少的技能触发概率超过 ${\displaystyle 0.55}$\displaystyle 0.55。即使我们将比例从 ${\displaystyle 1.5}$\displaystyle 1.5 放宽到 ${\displaystyle 2}$\displaystyle 2，那也只能因对名义概率 ${\displaystyle p>0.4}$\displaystyle p >0.4 的情形。而幻刺的恩赐解脱 ${\displaystyle p=0.15}$\displaystyle p=0.15，${\displaystyle c\approx 0.0322}$\displaystyle c\approx 0.0322，采用PRD算法，在最极端情况下会出现连续31次不暴击（概率为 ${\displaystyle 6.661338\times {10}^{-16}}$\displaystyle 6.661338\times 10^{-16}），一局比赛对英雄的攻击次数可能也就 ${\displaystyle 200\sim 300}$\displaystyle 200\sim 300 次左右，出现这种极端情形将会严重影响游戏体验。假如在刚暴击过一次之后立刻去参加团战，一次团战如果攻击 ${\displaystyle 10}$\displaystyle 10 次，这 ${\displaystyle 10}$\displaystyle 10 次都不暴击的概率高达 ${\displaystyle 13.33755\mathrm{\%}}$\displaystyle 13.33755\%，${\displaystyle 15}$\displaystyle 15 次攻击不出暴击的概率也有 ${\displaystyle 0.8704117\mathrm{\%}}$\displaystyle 0.8704117\%，一次团战可能就失败了。PRD算法并没有很好地完成减少极端情况的任务，究其原因，是PRD算法的自由度太低了，在给定名义概率 ${\displaystyle p}$\displaystyle p 后， ${\displaystyle c}$\displaystyle c 和 ${\displaystyle N}$\displaystyle N 的值都可以完全确定下来。在这个意义下，PRD算法可能还不如我在上一篇文章中介绍的简单保底机制，因为在那里，给定名义概率后 ${\displaystyle p}$\displaystyle p，保底次数 ${\displaystyle N}$\displaystyle N 可以自由选取，只需满足 ${\displaystyle N⩾1/p}$\displaystyle N\geqslant 1/p 即可， ${\displaystyle p}$\displaystyle p 和 ${\displaystyle N}$\displaystyle N 固定后， ${\displaystyle c}$\displaystyle c 的值可以通过公式计算出来，我们可以把 ${\displaystyle N}$\displaystyle N 选的比较靠近期望次数 ${\displaystyle 1/p}$\displaystyle 1/p 来减少极端情况，不过这样可能会导致算法固定在第 ${\displaystyle N}$\displaystyle N 次左右才给出成功结果。

得想办法前面的保底机制进行修改，让最大次数 ${\displaystyle N}$\displaystyle N 不要比平均次数 ${\displaystyle 1/p}$\displaystyle 1/p 大太多，同时表现出一定的随机性，让人不要太容易预测。我在这里给出一种可能得解决方案。回顾简单保底机制的转移矩阵 $$P=\left(\begin{array}{ccccccc}c& 1-c& & & & & \\ c& & 1-c& & & & \\ c& & & 1-c& & & \\ ⋮& & & & \ddots & & \\ c& & & & & 1-c& \\ 1& & & & & 0& \end{array}\right)\begin{array}{c}0\\ 1\\ 2\\ ⋮\\ N-2\\ N-1\end{array}$$P=\begin{pmatrix} c & 1-c & & & & & \\ c & & 1-c & & & & \\ c & & & 1-c & & & \\ \vdots & & & & \ddots & & \\ c & & & & & 1-c & \\ 1 & & & & & 0 & \end{pmatrix}\begin{matrix} 0\\ 1\\ 2\\ \vdots \\ N-2\\ N-1 \end{matrix}\\以及本文里的PRD算法对应的转移矩阵，这两个矩阵长得很像，在相同的位置为 ${\displaystyle 0}$\displaystyle 0 或非 ${\displaystyle 0}$\displaystyle 0，差别只是非 ${\displaystyle 0}$\displaystyle 0 位置的数字，我们可以修改这些数字，不需要拘泥于常数，或者线性增长，采用非线性的变化，只需要满足修改后还是一个不可约的转移矩阵即可，修改后的名义概率可以用这两篇文章里展示的两种方法计算。一个例子就是原神抽卡，前一段是常数，后一段线性增长，我们会在之后的文章中对原神的抽卡机制进行分析。更进一步，甚至可以将一部分 ${\displaystyle 0}$\displaystyle 0 改成非 ${\displaystyle 0}$\displaystyle 0，增加过程的随机性，但这样的修改需要非常仔细，因为这可能会导致保底次数 ${\displaystyle N}$\displaystyle N 的失效，也就是无法保证 ${\displaystyle N}$\displaystyle N 次之内一定成功。最后再配合上上一篇文章提到的将不同状态分配给不同的随机结果（不同稀有度），这会给出非常有趣的保底机制。

爱笑的男孩运气不会太差，但也不会太好

我们一直拿Dota2举例，所以这次我们来算一个Moba玩家可能会关心的问题，在PRD机制下，如果名义概率为 ${\displaystyle p}$\displaystyle p，那连续两次暴击的概率是多少，在独立随机的情况下，连续两次暴击的概率显然是 ${\displaystyle p^2}$\displaystyle p^{2}。会有人问PRD算法既然是一种保底算法，让我们的运气不要太差，那是不是也会让连续成功概率变高呢。这里先给出结论，答案是否定的，事实上我们可以证明在连续两次暴击的出现频率会趋向于 ${\displaystyle pc}$\displaystyle pc，而 ${\displaystyle c<p}$\displaystyle c< p，所以连续两次暴击的概率是严格小于独立随机的情形的，非常可惜，好运也同时被PRD算法削减了。连续 ${\displaystyle k}$\displaystyle k 次暴击的概率是 ${\displaystyle p{c}^{k-1}}$\displaystyle pc^{k-1}，严格小于独立情形中的 ${\displaystyle p^k}$\displaystyle p^{k}， ${\displaystyle k}$\displaystyle k 越大差距越大。这些概率的计算方法将会放在之后的文章里。

当然我们也不要太消极，对于PRD算法，在参加团战之前，我们可以多攻击几次，让自己处于一个较大的状态 ${\displaystyle k}$\displaystyle k，后续短期的团战中，暴击概率高于名义概率 ${\displaystyle p}$\displaystyle p，最低要求是 ${\displaystyle (k+1)c⩾p}$\displaystyle ( k+1) c\geqslant p，例如幻刺需要在上一次暴击后积攒至少 ${\displaystyle 4}$\displaystyle 4 次不暴击，点了 ${\displaystyle 22\mathrm{\%}}$\displaystyle 22\% 暴击天赋的话减少为 ${\displaystyle 3}$\displaystyle 3 次。需要注意是至少这么多次，积攒的越多，团战暴击概率越高，当然积攒多次不暴击的难度也会变大。

暂定的后续内容一篇是关于原神的抽卡机制，还有一篇是一些零碎的内容。